//
// Created by TNJ on 2021/6/10.
//
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

static node_t *new_node(int data){
    node_t *node = (node_t *)malloc(sizeof(node_t));
    if(node == NULL){
        return NULL;
    }
    node->next = NULL;
    node->data = data;

    return node;
}

static void free_node(node_t *node){
    if(node == NULL){
        return;
    }
    free(node);
    node->next = NULL;
}

void queue_init(queue_t *q){
    if(q == NULL){
        return;
    }
    q->head = NULL;
    q->tail = NULL;
}

void enqueue(queue_t *q, int data){
    if(q == NULL){
        return;
    }
    node_t *node = new_node(data);  //新建一个结点
    if(node == NULL){
        return;
    }
    if(q->head == NULL && q->tail == NULL){
        //首次插入一个结点
        q->tail = node;
        q->head = node;
        return;
    }
    q->tail->next = node;
    q->tail = node;
}

int dequeue(queue_t *q){
    if(q == NULL){
        return NAN;
    }
    if(q->head == NULL && q->tail == NULL){
        return NAN;
    }
    node_t *node = q->head;
    int data = node->data;
    if(q->head->next == q->tail){
        //只有一个结点
        q->head = NULL;
        q->tail = NULL;
    }else{
        //不止一个结点
        q->head = q->head->next;
    }
    node->next = NULL;
    free_node(node);

    return data;
}

int queue_length(queue_t *q){
    if(q == NULL){
        return 0;
    }
    node_t *node = q->head;
    if(node == NULL){
        return 0;
    }
    int length = 1;
    while(node != q->tail){
        node = node->next;
        length++;
    }
    return length;
}

void queue_destroy(queue_t *q){
    if(q == NULL){
        return;
    }
    node_t *node = q->head;
    if(node == NULL){
        return;
    }
    node_t *temp = NULL;
    while(node->next != q->tail){
        temp = node;
        node = node->next;
        free_node(temp);
        temp = NULL;
    }
    free_node(node);
    q->tail = NULL;
    q->head = NULL;
}

void queue_arr_init(queue_arr_t *q, int capacity){
    if(q == NULL || capacity <= 0){
        return;
    }
    q->head = 0;
    q->tail = 0;
    q->size = 0;
    q->arr = malloc(capacity * sizeof(int));
    q->cap = capacity;
}

void enqueue_arr(queue_arr_t *q, int data){
    if(q == NULL){
        return;
    }
    if(queue_arr_is_full(q)){
        return;
    }
    //循环重用使用过的内存
    if(q->tail >= q->cap){
        q->tail = 0;
    }
    q->arr[q->tail++] = data;
    q->size++;
}

int dequeue_arr(queue_arr_t *q){
    if(q == NULL){
        return NAN;
    }
    if(queue_arr_is_empty(q)){
        return NAN;
    }
    if(q->head >= q->cap){
        q->head = 0;
    }
    q->size--;
    return q->arr[q->head++];
}

void queue_arr_destroy(queue_arr_t *q){
    if(q == NULL){
        return;
    }
    if(q->arr){
        free(q->arr);
    }
    q->arr = NULL;
    q->tail = 0;
    q->head = 0;
    q->cap = 0;
    q->size = 0;
}

bool queue_arr_is_full(queue_arr_t *q){
    if(q == NULL){
        return false;
    }
    return q->size == q->cap ? true : false;
}

bool queue_arr_is_empty(queue_arr_t *q){
    if(q == NULL){
        return true;
    }
    return q->size == 0 ? true : false;
}

int queue_arr_length(queue_arr_t *q){
    if(q == NULL){
        return 0;
    }
    return q->size;
}
